Recent Denial-of-Service (DoS) attacks on major e-commerce web sites, like yahoo.com, amazon.com and ebay.com, have been very successful in disrupting their Internet activity for a considerable period of time. The popularity of DoS attacks in the hacker-community may be attributed to the vulnerability of interconnected computer systems and the ease with which DoS attacks can be launched over the Internet. SYN Flooding attacks are one of the most popular forms of DoS attacks that exploit the TCP's 3-way handshake connection mechanism and its limitation in maintaining the ‘Incomplete Connection Queue.’
To initiate a normal TCP connection, the client sends a SYN packet to the server. The server creates a new entry on the ‘incomplete connection queue’ for the SYN packet that has arrived, and responds by sending a SYN+ACK packet back to the initiating client. The client then acknowledges the server by sending an ACK packet (generally, ACK=SYN+ACK+1), thus completing the TCP 3-way handshake. See FIG. 1. Once the final ACK is received from the client, the entry in the incomplete connection queue for this connection is discarded. Most Berkeley-derived TCP implementations maintain an Incomplete Connection Queue for each listening socket (for instance, for a FTP server, an Email server, or a Web server). An entry remains on the Incomplete Connection Queue (“ICQ”) until the SYN+ACK packet is acknowledged by the client, or until the entry times out. The connection timeout for each entry is typically set to 75 seconds.
To launch a SYN Flooding attack, an attacker floods the victim server with a huge number of SYN packets originating from spoofed IP sources. Attempted connection has an associated entry in the ICQ. The server responds to the SYN packet with the return ACK. However, the initiating “client” fails to respond to the ACK with the SYN+ACK, hence, leaving the entry in the ICQ for this attempt until time out. With a sufficient number of attempts, the ICQ will completely fill, overwhelming the system due to the inability to log new incoming calls in the ICQ. Due to a filled ICQ, the server rejects all incoming connections, even those originating from legitimate sources, causing a denial of service. To clear the system, it may be necessary to shut down and restart, resulting in downtime and data loss.
Prior art in attack detection schemes can be classified into two categories: (1) ‘Stateful’ mechanisms, which maintain a per-connection state, and (2) ‘Stateless’ mechanisms which do not maintain a per-connection state. SYN Cache, SYN Cookies, Synkill and SynProxying are some examples of ‘Stateful’ approaches. The SYN Cache replaces the per-socket linear incomplete connection queue with a global hash table. The ‘Cachelimit’ parameter imposes an upper bound on the memory that the SYN Cache uses and the ‘BucketSize’ parameter limits number of entries per hash bucket, bounding the time required for searching the entries. An entry overflow is handled by performing a FIFO drop of an entry on the hash list. SYN Cookies replace the Syn Cache's overflow handling mechanism by sending a SYN Cookie instead of dropping an entry from the hash list. A cookie contains an Initial Sequence Number, which is returned in the final phase of the TCP's three way handshake. As connection establishment is performed by the returning ACK, a secret is used to validate the connection. The Synkill algorithm classifies the addresses of all incoming packets into ‘good’ or ‘evil’ classes based on observed network traffic and input supplied by the administrator. A decision process based on a finite state machine determines the correct state membership of each incoming packet and sends RST packets in response to deter connection establishment attempts from evil IP sources. SynProxying sets a threshold on the number of SYN packets per second passing through the firewall. On reaching the threshold, the firewall proxies all incoming SYN packets by storing the incomplete connections in a queue. The incomplete connections remain in the firewall until the connection is completed or the request times out. All ‘Stateful’ approaches are by themselves vulnerable to flooding attacks.
‘Stateless’ non-parametric algorithms based on Sequential and Batch-Sequential Change Point Detection theory to detect SYN Flooding attacks have been developed by Wang et al. “Detecting SYN Flooding Attacks,” Proceedings of IEEE Infocom, June 2002. This method uses the discrepancy between the SYN-FIN (RST) pairs to detect SYN flooding. The weakness in using the discrepancy between SYN-FIN pairs as a criterion for detecting SYN flooding is that an attacker can paralyze the detection mechanism by flooding a mixture of SYN and FIN (RST) packets. Moreover, change point detection based algorithms may be sensitive to daytime variations in the Internet traffic, increasing the number of false positives when the attack triggering threshold is inappropriately selected.